home *** CD-ROM | disk | FTP | other *** search
/ ETO Development Tools 2 / ETO Development Tools 2.iso / Tools - Objects / MacApp / MacApp CD Release / MacApp 2.0.1 (Many Libraries) / Interfaces / CIncludes / UList.h < prev    next >
Encoding:
C/C++ Source or Header  |  1990-10-25  |  26.6 KB  |  523 lines  |  [TEXT/MPS ]
  1. /*[a-,body+,h-,o=100,r+,rec+,t=4,u+,#+,j=20/57/1$,n-]*/
  2. /* UList.p */
  3. /* Copyright © 1984-1990 by Apple Computer Inc. All rights reserved. */
  4.  
  5. /* Unit UList defines object types TList, a simple dynamic array whose elements are references to
  6.   TObjects, and TSortedList, which maintains the object references in a sequence defined by
  7.   overriding TSortedList.Compare.
  8.     Peter Gaston's scheme for chunky memory allocation has been used by permission.
  9.     Thanks Peter!.
  10. TList:
  11.     TList is an object which provides a very nice dynamic array of objects.
  12.     It is implemented by appending the dynamic array onto the end of the
  13.     object.  Growing and shrinking the array is done by growing and shrinking
  14.     the handle which holds the object.
  15. TSortedList:
  16.     TSortedList maintains the object references in a sequence defined by
  17.     overriding TSortedList.Compare
  18. Some Specific uses that TList is especially good for.
  19.     LIFO Stack:
  20.         A push/pop operation is provided.
  21.     FIFO Stack: (Queue)
  22.         Use InsertLast for Queue and First for Dequeue.
  23.     Pre-allocation of your list:
  24.         If you know the size that your list will eventually reach, then you can
  25.         pre-set it to the proper size.
  26.     Delete by Index:
  27.         If you keep track of items by index number, then you can avoid
  28.         a linear search when you want to delete it. Remember though, it
  29.         is a dynamic list and any insertion/deletion activity can cause
  30.         the index to point at a different element than you expect.
  31. Caveats:
  32.     A _small_ amount of memory is always wasted with this method.  An active
  33.     list will generally waste one-half of the chunk size, or
  34.     4*2=8 bytes/TList.
  35. */
  36. #ifndef  __UList__
  37. #define __UList__  0
  38. #endif
  39. #if  ! __UList__
  40. #define __UList__  1
  41.  
  42.         /* • Auto-Include the requirements for this unit's interface. */
  43. #ifndef  __UObject__
  44. #include "UObject.h"
  45. #endif
  46.  
  47. const short kAllocationIncrement = 6;                    /* Initial Allocation increment. Six
  48.                                                          elements of slop shouldn't break anybody
  49.                                                          and provides a _nice_ cushion from the
  50.                                                          memory manager. */
  51. const short kIterateForward        = true;
  52. const short kIterateBackward    = ! kIterateForward;
  53.  
  54. const short kEmptyIndex            = 0;                    /* Value to use when no valid index is
  55.                                                          available Indexes are always positive */
  56.  
  57.             /* Constants for TSortedList.Compare */
  58. const short kItem1LessThanItem2 = - 1;
  59. const short kItem1EqualItem2    = 0;
  60. const short kItem1GreaterThanItem2 = 1;
  61.  
  62. const short kALessThanB            = kItem1LessThanItem2;    /* Left in for compatibility (2.0) */
  63. const short kAEqualB            = kItem1EqualItem2;        /* Left in for compatibility (2.0) */
  64. const short kAGreaterThanB        = kItem1GreaterThanItem2; /* Left in for compatibility (2.0) */
  65.  
  66.             /* Constants for TSortedList.Search.
  67.             The criteria is considered to be item 2*/
  68. const short kItemGreaterThanCriteria = kItem1LessThanItem2;
  69. const short kItemEqualCriteria    = kItem1EqualItem2;
  70. const short kItemLessThanCriteria = kItem1GreaterThanItem2;
  71.  
  72. typedef struct PtrBasedDoublyLinkedListNode *PtrBasedDoublyLinkedListNodePtr; 
  73. struct PtrBasedDoublyLinkedListNode {
  74.     PtrBasedDoublyLinkedListNodePtr previousLink;                     /* link to previous node */
  75.     PtrBasedDoublyLinkedListNodePtr nextLink;                         /* link to next node */
  76. };
  77.  
  78. class TPtrBasedDoublyLinkedList : public TObject {
  79.   public:
  80.    /* Manages a doubly linked list of nodes.
  81.                                                           The nodes are pointer based since they
  82.                                                           will typically be on the stack */
  83.     PtrBasedDoublyLinkedListNodePtr fHeadNodePtr;                     /* HEAD of the linked list */
  84.     PtrBasedDoublyLinkedListNodePtr fTailNodePtr;                     /* TAIL of the linked list */
  85.                                 /*Creation/Destruction Methods*/
  86.  
  87.     virtual pascal void IPtrBasedDoublyLinkedList(void);
  88.                 /* Initialize a new linked list.*/
  89.  
  90.     virtual pascal void AppendNode(void *thisNode);
  91.                 /* Add a new node to the list */
  92.  
  93.     virtual pascal void RemoveNode(void *thisNode);
  94.                 /* Remove a node from the list */
  95.  
  96.     virtual pascal void EachNodeDo(pascal void (*DoToNode)(void *thisNode, void *DoToNode_StaticLink
  97.        ), void *DoToNode_StaticLink);
  98.                 /* Call do to node for each node in the list, passing a pointer to the node as a
  99.                 parameter to the called procedure. */
  100.  
  101.                 /* Debugging Methods */
  102.  
  103.     virtual pascal void Fields(pascal void (*DoToField)(StringPtr fieldName, Ptr fieldAddr, short 
  104.        fieldType, void *DoToField_StaticLink), void *DoToField_StaticLink);
  105.                 /* Used by the Inspector and the Debugger to display the contents of this class's
  106.                 fields. */
  107.  
  108. };
  109.  
  110. typedef unsigned long ArrayIndex;                           /* At least always positive ( in this
  111.                                                             universe ) !!! kEmptyIndex..MaxLong
  112.                                                             would be a nice enhancement */
  113. typedef short CompareResult;                            /* Negative, zero, and positive results are
  114.                                                          all meaningful even though we have the
  115.                                                          nice constants above. */
  116.  
  117.  
  118. typedef struct IterationNode *IterationNodePtr; 
  119. struct IterationNode {
  120.     IterationNodePtr previousLink;                        /* link to previous iteration record */
  121.     IterationNodePtr nextLink;                            /* link to next iteration record */
  122.     ArrayIndex iterLowBound;                            /* lower bound of iteration in progress */
  123.     ArrayIndex iterIndex;                                /* current index of this iteration */
  124.     ArrayIndex iterHighBound;                            /* upper bound of iteration in progress */
  125.     Boolean iterForward;                                /* if iteration is forward or backward
  126.                                                          through the list */
  127. };
  128.  
  129. class TDynamicArray : public TPtrBasedDoublyLinkedList {
  130.   public:     /* TDynamicArrays don't really
  131.                                                                       have an IS A relationship
  132.                                                                       with
  133.                                                                       TPtrBasedDoublyLinkedList but
  134.                                                                       have a HAS A relationship
  135.                                                                       with it. We subclass it here,
  136.  
  137.                                                                       however, because to have a
  138.                                                                       HAS A relationship with it
  139.                                                                       would require *YET ANOTHER*
  140.                                                                       object in the heap and this
  141.                                                                       dynamically sized object
  142.                                                                       stuff is supposed to help
  143.                                                                       reduce that need. */
  144.     ArrayIndex fSize;                                    /* number of elements ACTUALLY in the array,
  145.  
  146.                                                          from 0 to the limit of memory*/
  147.     short fElementSize;                                    /* Size in bytes of an element. MUST be a
  148.                                                          power of 2 ie. 1, 2, 4, 8, 16, etc. */
  149.     short fElementSizeShift;                            /* the power of 2 for the element size. Will
  150.                                                          be used to avoid DIV and MUL */
  151.  
  152.     ArrayIndex fAllocationIncrement;
  153.        /* Number of elements by which to increase of
  154.                                                          decrease the allocated size of the array
  155.                                                          when it needs to grow or shrink. Thus
  156.                                                          reducing memory manager aggravation. */
  157.     ArrayIndex fAllocatedSize;                            /* Number of elements for which storage is
  158.                                                          ALLOCATED */
  159.     Boolean fFreeRequested;                                /* TRUE if the Free method was called but
  160.                                                          couldn't be honored because enumeration
  161.                                                          was in process. Checked at end of
  162.                                                          enumeration and Free is called if true */
  163.     Size fClassSize;                                    /* Used with ComputeAddress to create a
  164.                                                         pointer to an element.  This breaks
  165.                                                         encapsulation of GetDynamicArea 
  166.    but, is being
  167.                                                         done here for performance reasons (small) */
  168.                                 /*Creation/Destruction Methods*/
  169.  
  170.     virtual pascal void IDynamicArray(ArrayIndex initialSize, short elementSize);
  171.                 /* Initialize a new array with initialSize elements, Always call it once before
  172.                 calling any other method.  Never call it twice.*/
  173.  
  174.                 /* Array manipulation primitives */
  175.  
  176.     virtual pascal ArrayIndex GetSize(void);
  177.                 /* Returns the ACTUAL number of elements in the array.*/
  178.  
  179.     virtual pascal void SetArraySize(ArrayIndex theSize);
  180.                 /* Sets the array allocation to handle up to theSize elements */
  181.  
  182.     virtual pascal ArrayIndex EachElementDoTil(pascal Boolean (*TestElement)(ArrayIndex elementIndex
  183.        , void *TestElement_StaticLink), void *TestElement_StaticLink, Boolean IterateForward);
  184.  
  185.      /* The basic array iterator. Call TestIndex once for each element of the array, in order,
  186.  
  187.                 until TestIndex returns TRUE.
  188.                   Return the element that satisfied the test.  If none satisfied the tes
  189.    t, return kEmptyIndex.
  190.                 */
  191.     virtual pascal void Free(void);
  192.                 /* If enumeration of the array is in process, delete all the array elements,
  193.  
  194.                 mark the fFreeRequested flag for testing at completion of the enumeration and
  195.                 return.  Otherwise really free the array.  Gee, wouldn't automatic storage
  196.                 management be great! */
  197.  
  198.     virtual pascal void InsertElementsBefore(ArrayIndex index, void *ElementPtr, ArrayIndex count);
  199.                 /* Insert Elements before the indicated Element. The index of the new element
  200.                   will be index.   If index = 1 this inserts at the start of the array. 
  201.    If index = fSize + 1
  202.                   this inserts at the end of the array. Signals Failure if unable to cha
  203.    nge the size of
  204.                   the array.
  205.                   !!! NOTE MULTIPLE ( >1 ) element moves for non-power of 2 element sizes are NOT
  206.                   yet supported! */
  207.  
  208.     virtual pascal void ReplaceElementsAt(ArrayIndex index, void *ElementPtr, ArrayIndex count);
  209.                 /* Replaces the Elements at the indicated index.
  210.                   !!! NOTE MULTIPLE ( >1 ) element moves for non-power of 2 element sizes are NOT
  211.                   yet supported! */
  212.  
  213.     virtual pascal void DeleteElementsAt(ArrayIndex index, ArrayIndex count);
  214.                 /* Deletes the Element at the indicated index.  Compresses the array
  215.                   !!! NOTE MULTIPLE ( >1 ) element moves for non-power of 2 element sizes are NOT
  216.                   yet supported! */
  217.  
  218.     virtual pascal void GetElementsAt(ArrayIndex index, void *ElementPtr, ArrayIndex count);
  219.                 /* copies count elements to the location specified by ptr.
  220.                   !!! NOTE MULTIPLE ( >1 ) element moves for non-power of 2 element sizes are NOT
  221.                   yet supported! */
  222.  
  223.     virtual pascal Ptr ComputeAddress(ArrayIndex index);
  224.                 /* Returns a pointer to of the index-th element in the array.
  225.                 PLEASE NOTE: The return value is a direct heap pointer and should be used with
  226.                 care as the heap can compact across calls that move memory; thus invalidating
  227.                 the pointer. */
  228.  
  229.                 /* Misc. functions */
  230.  
  231.     virtual pascal Boolean IsEmpty(void);
  232.                 /* Test if this array is empty or not. */
  233.  
  234.     virtual pascal void Merge(TDynamicArray *aDynamicArray);
  235.                 /* merges aDynamicArray with itself. leaves aDynamicArray unchanged.
  236.                   !!! NOTE MULTIPLE ( >1 ) element moves for non-power of 2 element sizes are NOT
  237.                   yet supported! */
  238.  
  239.                 /* Debugging Methods */
  240.  
  241.     virtual pascal void Fields(pascal void (*DoToField)(StringPtr fieldName, Ptr fieldAddr, short 
  242.        fieldType, void *DoToField_StaticLink), void *DoToField_StaticLink);
  243.                 /* Used by the Inspector and the Debugger to display the contents of this class's
  244.                 fields. */
  245.  
  246.     virtual pascal void DynamicFields(pascal void (*DoToField)(StringPtr fieldName, Ptr fieldAddr, 
  247.        short fieldType, void *DoToField_StaticLink), void *DoToField_StaticLink);
  248.                 /* Used by the Inspector and the Debugger to display the contents of this class's
  249.                 dynamic area. */
  250.  
  251. };
  252.  
  253. class TList : public TDynamicArray {
  254.   public:             /*A dynamic list of TObjects. It IS
  255.                                                           permissible for descendants to add more
  256.                                                           named fields*/
  257.     ObjClassID fObjClassID;                                /* if <> kNilClass then the Class ID of the
  258.                                                          elements of the list */
  259.                                 /*Creation/Destruction Methods*/
  260.  
  261.     virtual pascal void IList(void);
  262.                 /* Initialize a new list with no elements, i.e., fSize = 0.  Always
  263.                   call it once before calling any other method.  Never call it
  264.                   twice.*/
  265.  
  266.     virtual pascal void FreeList(void);
  267.                 /* Frees each object in the list, then frees the list.*/
  268.  
  269.                 /* Utility Methods*/
  270.  
  271.     virtual pascal TObject *At(ArrayIndex index);
  272.  
  273.        /* Return the index'th element of the list. It is typical for the caller to coerce the
  274.                 result into a descendant of TObject. All lists are indexed from 1. Range check only
  275.                 if the compile-flag qRangeCheck is TRUE. The static-array equivalent of:
  276.                 object := objList.At(index); is: object := objArray[index]; */
  277.  
  278.     virtual pascal ArrayIndex GetEqualItemNo(TObject *item);
  279.  
  280.       /* Return the index of the item in the list, or zero if the item is not in the list. */
  281.  
  282.     virtual pascal ArrayIndex GetSameItemNo(TObject *item);
  283.  
  284.       /* Return the index of the IDENTITY item in the list, or zero if the item is not in the
  285.                 list. */
  286.  
  287.     virtual pascal TObject *First(void);
  288.                 /* Return the first element of the list. It is typical for the caller to coerce the
  289.                 result. Returns NIL if the size is <= 0. */
  290.  
  291.     virtual pascal TObject *Last(void);
  292.                 /* Return the last element of the list. It is typical for the caller to coerce the
  293.                 result. Returns NIL if the size is <= 0. */
  294.  
  295.                 /*Iterator Methods*/
  296.  
  297.     virtual pascal TObject *IterateTil(pascal Boolean (*TestItem)(TObject *item, void *
  298.        TestItem_StaticLink), void *TestItem_StaticLink, Boolean IterateForward, ArrayIndex *itsIndex
  299.        );
  300.  
  301.       /* The basic list iterator.  Call TestItem once for each element of the list, in order,
  302.  
  303.                 until TestItem returns TRUE.
  304.                   Return the element that satisfied the test.  If none satisfied the tes
  305.    t, return NIL.
  306.                   The actual parameter is typically a procedure whose argument is a desc
  307.    endant of TObject.
  308.                   It is typical for the caller to coerce the result into that descendant of TObject.
  309.                   If TestItem calls InsertLast, the newly added element will NOT be enumerated.
  310.                   If TestItem calls AtPut, InsertBefore, InsertFirst, or DeleteAll, misbehavior will
  311.                   ensue.  The static-array equivalent of:
  312.                     object := objList.FirstThat(Func)
  313.                   is:
  314.                     object := NIL;
  315.                     FOR index := 1 TO fSize DO IF Func(objArray[index]) THEN
  316.                         BEGIN
  317.                         object := objArray[index];
  318.                         LEAVE;
  319.                         END;
  320.                 */
  321.  
  322.     virtual pascal void Each(pascal void (*DoToItem)(TObject *item, void *DoToItem_StaticLink), void
  323.         *DoToItem_StaticLink);
  324.  
  325.         /* Call DoToItem once for each element of the list, in order. The actual parameter is
  326.                 typically a procedure whose argument is a descendant of TObject. If DoToItem calls
  327.                 InsertLast, the newly added element will NOT be enumerated. If TestItem calls
  328.                 AtPut, InsertBefore, InsertFirst, Delete, or DeleteAll, misbehavior will ensue. If
  329.                 DoToItem calls Delete, the item is replaced by the constant kDeletedElement; fSize
  330.                 is decremented and fDeletions is incremented. At the end of all calls to Each,
  331.  
  332.                 TList.RemoveDeletions will be called. The static-array equivalent of:
  333.                 objList.Each(Proc) is:
  334.                 FOR index := 1 TO fSize DO
  335.                     Proc(objArray[index]);
  336.                 */
  337.  
  338.     virtual pascal TObject *FirstThat(pascal Boolean (*TestItem)(TObject *item, void *
  339.        TestItem_StaticLink), void *TestItem_StaticLink);
  340.                 /* Call TestItem once for each element of the list, in order, until TestItem returns
  341.                 TRUE. Return the element that satisfied the test. If none satisfied the test,
  342.  
  343.                 return NIL. The actual parameter is typically a procedure whose argument is a
  344.                 descendant of TObject. It is typical for the caller to coerce the result into that
  345.                 descendant of TObject. If TestItem calls InsertLast, the newly added element will
  346.                 NOT be enumerated. If TestItem calls AtPut, InsertBefore, InsertFirst, Delete, or
  347.                 DeleteAll, misbehavior will ensue. */
  348.  
  349.     virtual pascal TObject *LastThat(pascal Boolean (*TestItem)(TObject *item, void *
  350.        TestItem_StaticLink), void *TestItem_StaticLink);
  351.  
  352.        /* Call TestItem once for each element of the list, starting with the last item in the
  353.                 list and working toward the first item, until TestItem returns TRUE. Return the
  354.                 element that satisfied the test. If none satisfied the test, return NIL. The actual
  355.                 parameter is typically a procedure whose argument is a descendant of TObject. It is
  356.                 typical for the caller to coerce the result into that descendant of TObject. If
  357.                 TestItem calls InsertLast, the newly added element will NOT be enumerated. If
  358.                 TestItem calls AtPut, InsertBefore, InsertFirst, Delete, or DeleteAll, misbehavior
  359.                 will ensue. */
  360.  
  361.                 /*Item Insertion Methods*/
  362.  
  363.     virtual pascal void AtPut(ArrayIndex index, TObject *newItem);
  364.                 /* Replace the index'th item of the list. Does not free the old item. If you do this
  365.                 from within an Each the results will be unpredictable.*/
  366.  
  367.     virtual pascal void Insert(TObject *item);
  368.                 /* Inserts the given item into the list in arrival sequence. */
  369.  
  370.     virtual pascal void InsertBefore(ArrayIndex index, TObject *item);
  371.                 /* Insert a reference to an item before the indicated item. The index of the new
  372.                 element will be index. If index = 1 this inserts at the start of the list. If index
  373.                 = fSize + 1 this inserts at the end of the list. Signals Failure if unable to
  374.                 increase the size of the list.*/
  375.  
  376.     virtual pascal void InsertFirst(TObject *item);
  377.  
  378.         /* Insert a reference to item at the front of the list. If the compile-flag qDebug is
  379.                 TRUE & SetEltType was called, verify item's type. Increase fSize by 1. The index of
  380.                 the new element will be 1. Signals Failure if unable to increase the size of the
  381.                 list.*/
  382.  
  383.     virtual pascal void InsertLast(TObject *item);
  384.                 /* Insert a reference to item at the back of the list. If the compile-flag qDebug is
  385.                 TRUE & SetEltType was called, verify item's type. Increase fSize by 1. The index of
  386.                 the new element will be fSize. Signals Failure if unable to increase the size of
  387.                 the list.*/
  388.  
  389.                 /*Item Deletion Methods*/
  390.  
  391.     virtual pascal void AtDelete(ArrayIndex index);
  392.                 /* Deletes via an index (rather than having to search for an item) */
  393.  
  394.     virtual pascal void Delete(TObject *item);
  395.                 /* Delete the first reference to item from the list, but do not free item. If item
  396.                 does not occur, do nothing. If item does occur, reduce fSize by 1.
  397.                 !!! NOTE: This name conflicts with the Pascal builtin: DELETE and we will be
  398.                 changing it's name, but changing the name at the _last minute_ isn't a good idea.
  399.                 If you need to use the builtin DELETE in a TList subclass, then you will have to
  400.                 create a wrapper procedure that forwards to it, for now. Sorry… the Management. */
  401.  
  402.     virtual pascal void DeleteAll(void);
  403.  
  404.       /* Delete every element from the list, but do not free any objects. Leave fSize at 0.*/
  405.  
  406.     virtual pascal void FreeAll(void);
  407.                 /* Frees each element in the list.  Leave fSize at 0.*/
  408.  
  409.                 /* Misc. functions */
  410.  
  411.     virtual pascal void SortBy(pascal CompareResult (*CompareItems)(TObject *item1, TObject *item2, 
  412.        void *CompareItems_StaticLink), void *CompareItems_StaticLink);
  413.                 /* Sorts the list using the supplied CompareItems function.   Uses Shell sort (see
  414.                 Sedgewick, "Algorithms", pp. 97-9)  */
  415.  
  416.     virtual pascal void Push(TObject *item);
  417.                 /* LIFO stack push.(same as insertLast) */
  418.  
  419.     virtual pascal TObject *Pop(void);
  420.                 /* LIFO stack pop. */
  421.  
  422.                 /* Debugging Methods */
  423.  
  424.     virtual pascal void SetEltType(StringPtr toClass);
  425.                 /* Call this once and pass the className of objects you intend to insert into the
  426.                 list. The TList insert methods will do a coercion to he type you specify, to ensure
  427.                 that the list contains only elements of the right type.*/
  428.  
  429.     virtual pascal void SetEltTypeID(ObjClassID toClassID);
  430.                 /* Call this once and pass the ObjClassID of objects you intend to insert into the
  431.                 list. The TList insert methods will do a coercion to the type you specify, to
  432.                 ensure that the list contains only elements of the right type.*/
  433.  
  434.     virtual pascal void Fields(pascal void (*DoToField)(StringPtr fieldName, Ptr fieldAddr, short 
  435.        fieldType, void *DoToField_StaticLink), void *DoToField_StaticLink);
  436.                 /* Used by the Inspector and the Debugger to display the contents of this class's
  437.                 fields. */
  438.  
  439.     virtual pascal void DynamicFields(pascal void (*DoToField)(StringPtr fieldName, Ptr fieldAddr, 
  440.        short fieldType, void *DoToField_StaticLink), void *DoToField_StaticLink);
  441.                 /* Used by the Inspector and the Debugger to display the contents of this class's
  442.                 dynamic area. */
  443.     virtual pascal void GetInspectorName(StringPtr inspectorName);
  444.                 /* Used by the Inspector to display the name of this class. */
  445.  
  446. };
  447.  
  448. class TSortedList : public TList {
  449.   public:            /* A sorted list of TObjects. Items are
  450.                                                          sorted based on the results of Compare
  451.                                                          which has to be overridden to provide a
  452.                                                          comparison mechanism. */
  453.     virtual pascal void ISortedList(void);
  454.                 /* Initialize a sorted list */
  455.  
  456.     virtual pascal TObject *DoSearch(pascal CompareResult (*TestItem)(TObject *anItem, void *
  457.        TestItem_StaticLink), void *TestItem_StaticLink, ArrayIndex *index);
  458.                 /* Searches the sorted list until TestItem returns zero or there are no more
  459.                   items to search.  A binary search is used. */
  460.  
  461.     virtual pascal ArrayIndex GetEqualItemNo(TObject *item);
  462.                 /* Return the index of any item that is considered to be equal to the parameter
  463.                 'item'. Two items are considered equal if comparing them with the Compare method
  464.                 returns zero. You may wish to use the constants kItemGreaterThanCriteria,
  465.  
  466.                 kItemEqualCriteria, kItemLessThanCriteria. */
  467.  
  468.     virtual pascal void Insert(TObject *item);
  469.                 /* Inserts the given item into the list in sorted order, using the Compare
  470.                   method to determine the item's location relative to other items in the list. */
  471.  
  472.     virtual pascal CompareResult Compare(TObject *item1, TObject *item2);
  473.  
  474.         /* This method compares two items in the list. A negative result indicates that item1
  475.                 < item2. A result of zero indicates that item1 = item2. A positive result indicates
  476.                 that item1 > item2. You may wish to use the constants kItem1LessThanItem2,
  477.  
  478.                 kItem1EqualItem2, kItem1GreaterThanItem2. By default just compare the ordinal value
  479.                 of the items. Subclasses that want to should override this method to do any other
  480.                 kind of comparison (comparing instance variables, for instance (get it?)). */
  481.  
  482.     virtual pascal TObject *Search(pascal CompareResult (*TestItem)(TObject *anItem, void *
  483.        TestItem_StaticLink), void *TestItem_StaticLink);
  484.                 /* This method searches the list of an item that causes your supplied TestItem
  485.                 function to return true. This is useful for cases in which you are not comparing
  486.                 objects in the list with another object, as does Compare. For example, suppose each
  487.                 object has an fTitle field and the objects are inserted into the list in order of
  488.                 fTitle. You can use the search method to look for an object whose fTitle is equal
  489.                 to any string. A negative TestItem result indicates that your search criteria <
  490.                 anItem, a result of zero indicates the item has been found and Search returns that
  491.                 item. A positive TestItem result indicates that your search criteria > your anItem.
  492.                 */
  493.  
  494.     virtual pascal void Sort(void);
  495.                 /* Sorts the list using TSortedList.Compare function and TList.SortBy.*/
  496.  
  497.     virtual pascal void Fields(pascal void (*DoToField)(StringPtr fieldName, Ptr fieldAddr, short 
  498.        fieldType, void *DoToField_StaticLink), void *DoToField_StaticLink);
  499.                 /* Used by the Inspector and the Debugger to display the contents of this class's
  500.                 fields. */
  501.  
  502. };
  503.  
  504. extern pascal TList *NewList(void);
  505.         /* A convenience function. Create a TList, initialize it, and return a reference to it.
  506.         Signals Failure if it cannot allocate the object.*/
  507.  
  508. extern pascal TSortedList *NewSortedList(void);
  509.         /* A convenience function. Create a TSortedList, initialize it, and return a reference t
  510.            o it.
  511.         Signals Failure if it cannot allocate the object.*/
  512.  
  513. extern pascal TList *NewAllocatedList(ArrayIndex iSize);
  514.         /* A convenience function. The same as NewList, but the initial allocation size can be s
  515.            et. */
  516.  
  517. extern pascal TList *FreeListIfObject(TList *list);
  518.         /* A convenience function. if list is non-nil then the same as list.FreeList.
  519.         Returns NIL for convenient assignment back to the reference passed in. */
  520.  
  521. #endif
  522.  
  523.